package com.lee.algorithm.sort;

/***
 * @description: 归并排序
 * @author : 青石路
 * @date: 2021/11/22 20:00
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{4,3,2,1,1,1,1,5,0};
        // System.out.println("small sum = " + smallSum(arr));
        reverseOrderPair(arr);
        SortUtil.print(arr);
    }

    /**
     * 先拆再合并
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    /**
     * 拆分
     * @param arr
     * @param left
     * @param right
     */
    public static void process(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) >> 1;
        process(arr, left, mid);            // 实现左边有序
        process(arr, mid+1, right);     // 实现右边有序
        merge(arr, left, mid, right);       // 合并全部，实现有序
    }

    /**
     * 合并，实现 arr[left] ~ arr[right] 有序
     *      left ~ mid 有序
     *      mid+1 ~ right 有序
     *      实现left ~ right 有序
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0, p1 = left, p2 = mid + 1;
        while (p1<=mid && p2 <= right) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2<=right) {
            help[i++] = arr[p2++];
        }
        for(i=0; i<help.length; i++) {
            arr[left+i] = help[i];
        }
    }

    /**
     * 求小和
     *      在一个数组中，每一个数左边比当前数小的数累加起来，就叫这个数组的小和
     *      边排序，边求小和
     * 如何做到不漏算、不重算
     *      不漏算：merge 过程中，会把某个数的右侧范围扩到整体
     *      不重算：已经变成一个部分的数据，在这个部分内不产生小和
     * @param arr
     * @return
     */
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return processSmallSum(arr, 0, arr.length - 1);
    }

    /**
     * 既排序，也求小和
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int processSmallSum(int[] arr, int left, int right) {
        if(left == right) {
            return 0;
        }
        int mid = (left + right) >> 1;
        return processSmallSum(arr, left, mid)                  // 左边小和
                + processSmallSum(arr, mid + 1, right)      // 右边小和
                + mergeSmallSum(arr, left, mid, right);         // 左右 merge 产生的小和
    }

    /**
     * 合并，并求小和
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @return
     */
    private static int mergeSmallSum(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0, p1 = left, p2 = mid + 1, smallSum = 0;
        while (p1<=mid && p2 <= right) {
            smallSum += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;     // 不排序的话，(right - p2 + 1) * arr[p1] 就用不了
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];              // 谁小谁拷贝到help数组，相等先拷贝右边，保证拷贝左边的数的时候能够快速的知道右边有多少个数比它大
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2<=right) {
            help[i++] = arr[p2 ++];
        }
        for(i=0; i<help.length; i++) {
            arr[left+i] = help[i];
        }
        return smallSum;
    }

    /**
     * 逆序对
     *      在一个数组中，左边的数如果比右边的数大（不一定相邻），则这两个数构成一个逆序对，请打印所有逆序对
     * @param arr
     */
    public static void reverseOrderPair(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        processReverseOrderPair(arr, 0, arr.length-1);
    }

    /**
     * 排序
     * @param arr
     * @param left
     * @param right
     */
    public static void processReverseOrderPair(int[] arr, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) >> 1;
        processReverseOrderPair(arr, left, mid);
        processReverseOrderPair(arr, mid + 1, right);
        mergeReverseOrderPair(arr, left, mid, right);
    }

    // 4,3,2,1,1,1,1,5,0
    public static void mergeReverseOrderPair(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int i = 0, p1 = left, p2 = mid + 1;
        while (p1<=mid && p2 <= right) {
            if(arr[p1] > arr[p2]) {                                         //
                for (int j=p1; j<=mid; j++) {
                    System.out.println(arr[j] + " " + arr[p2]);
                }
            }
            help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];  // 谁小谁拷贝到help数组，相等先拷贝左边，保证拷贝右边的数的时候能够快速的知道左边有多少个数比它大
        }
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2<=right) {
            help[i++] = arr[p2 ++];
        }
        for(i=0; i<help.length; i++) {
            arr[left+i] = help[i];
        }
    }
}
